package com.swjd.sort;

import java.text.SimpleDateFormat;
import java.util.Arrays;
import java.util.Date;

/**
 * 快速排序
 *
 * @author 刘涛
 * @create 2021/9/28 20:18
 */
public class QuickSort {
    public static void main(String[] args) {
/*        int arr[] = {-9, 78, 0, 23, -567, 70};
        //       数组  第一个数的下标  最后一个数的下标
        quickSort(arr, 0, arr.length - 1);
        System.out.println(Arrays.toString(arr));*/

        //测试快速排序速度  8万个数据测试
        long start = System.currentTimeMillis();
        int[] arr = new int[80000];
        for (int i = 0; i < 80000; i++) {
            arr[i] = (int) (Math.random() * 8000000);//生成[0,8000000)
        }
        quickSort(arr,0,arr.length-1);
        long end = System.currentTimeMillis();
        System.out.println("运行时长："+(end-start)+"ms");
    }

    /**
     * 快速排序
     *
     * @param arr   需要排序的数组
     * @param left  数组的第一个下标
     * @param right 数组的最后一个下标
     */
    public static void quickSort(int[] arr, int left, int right) {
        //把最初的第一个下标存储起来
        int l = left;
        //把最初的最后一个下标存储起来
        int r = right;
        //中间下标
        int center = arr[(left + right) / 2];
        //临时变量，交换使用
        int temp;
        //比中间小的放左边，比中间大的放右边
        while (left < right) {
            //如果左边值小于中间值就继续找，等在左边找到大于中间值的再去交换
            while (arr[left] < center) {
                left++;
            }
            //如果右边值大于中间值就继续找，等在右边找到小于中间值的再去交换
            while (arr[right] > center) {
                right--;
            }
            //左边下标已经扫描到要大于右边下标了 说明center两边的值已经分好了
            if (left >= right) {
                break;
            }
            //交换
            temp = arr[left];
            arr[left] = arr[right];
            arr[right] = temp;
            //当left指针等于中间值的时候,将右指针继续往中间靠,直到下标相等退出循环
            if (arr[left] == center) {
                right--;
            }
            //当left指针等于中间值的时候,将左指针继续往中间靠,直到下标相等退出循环
            if (arr[right] == center) {
                left++;
            }
        }
        //由于如果没有终止条件，下面两个if递归会一直递归下去，所以加上这个终止条件，同时当right == left下标相等时，也代表已经排序完成了
        if (right == left) {
            right--;
            left++;
        }
        //数组的第一个下标小于分组后的right的话，就进行排序
        if (l < right) {
            quickSort(arr, l, right);
        }
        //数组的最后一个下标大于分组后的left下标的话，就进行排序
        if (r > left) {
            quickSort(arr, left, r);
        }
    }
}
